#include <iostream>
#include <vector>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) :val(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* _buildTree(std::vector<int>& preorder, std::vector<int>& inorder, int& pos, int begin, int end)
    {
        if(begin > end)
        {
            pos--;
            return nullptr;
        }

        TreeNode* node = new TreeNode(preorder[pos]);
        if(begin == end)
            return node;

        //找到前序数组pos位置的值，在中序数组的位置
        int cur = begin;
        for(; cur < end; cur++)
        {
            if(inorder[cur] == preorder[pos])
                break;
        }
        
        pos++;
        node->left = _buildTree(preorder, inorder, pos, begin, cur - 1);
        pos++;
        node->right = _buildTree(preorder, inorder, pos, cur + 1, end);

        return node;
    }

    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        int preorder_index = 0;
        return _buildTree(preorder, inorder, preorder_index, 0, inorder.size() - 1);
    }
};